//数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1
//) 的解决方案。 
//
// 
//
// 示例 1： 
//
// 
//输入：[1,2,5,9,5,9,5,5,5]
//输出：5 
//
// 示例 2： 
//
// 
//输入：[3,2]
//输出：-1 
//
// 示例 3： 
//
// 
//输入：[2,2,1,1,1,2,2]
//输出：2 
//
// Related Topics 数组 计数 👍 243 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-09-16 00:00:21
 * @description 面试题 17.10.主要元素
 */
public class FindMajorityElementLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FindMajorityElementLcci fun=new FindMajorityElementLcci();
	 	 Solution solution = fun.new Solution();
		  solution.majorityElement(new int[]{3,2,3});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

	public int majorityElement(int[] nums) {
		// 第一次遍历：找到候选元素
		int candidate = nums[0];
		int count = 0;
		for (int num : nums) {
			if (count == 0) {
				candidate = num;
			}
			count += (num == candidate) ? 1 : -1;
		}

		// 第二次遍历：验证候选元素
		count = 0;
		for (int num : nums) {
			if (num == candidate) {
				count++;
			}
		}

		return count > nums.length / 2 ? candidate : -1;
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
